package link

import "errors"

// Node 定义节点
type Node struct {
	Data int
	Next *Node
}

// LinkedList 定义链表
type LinkedList struct {
	head   *Node
	length int
}

// Append 为链表添加节点的方法,可能发生参数校验错误
func (list *LinkedList) Append(node *Node) (err error) {
	// 不允许拼接空节点
	if node == nil {
		err = errors.New("node for append is nil")
		return
	}
	// 链表为空时
	if list.head == nil {
		list.head = node
		list.length++
	}

	// 找到最后一个节点
	lastNode := list.head
	for ; lastNode.Next != nil; lastNode = lastNode.Next {
	}
	lastNode.Next = node
	list.length++
	return
}

// removeAll 为链表删除节点的方法,元素不存在则删除失败
func (list *LinkedList) removeAll(Data int) (result int) {

	// 为统一代码逻辑，这里设置哨兵节点作为头节点
	newHead := &Node{0, list.head}
	for ; newHead.Next != nil; newHead = newHead.Next {
		// 先取出下个节点
		Next := newHead.Next
		if Next.Data == Data {
			newHead.Next = Next.Next
			list.length--
			result++
		}
	}

	// 移除哨兵节点
	list.head = newHead.Next
	return
}

// contains 包含判断
func (list *LinkedList) contains(Data int) (result bool) {

	for currNode := list.head; currNode != nil; currNode = currNode.Next {
		if currNode.Data == Data {
			result = true
			return
		}
	}

	return
}

// reserve 链表反转
func (list *LinkedList) reserve() {

	// 定义一个新链表，将旧链表上的数据逐一迁移到新链表
	var newHead *Node
	for oldHead := list.head; oldHead != nil; {
		// 取出旧链表的下一个节点
		Next := oldHead.Next
		// 将新旧链表节点加入新链表
		oldHead.Next = newHead
		newHead = oldHead
		// 将旧链表头指向其下一个节点
		oldHead = Next
	}
	// 将链表头指向新节点
	list.head = newHead
	// 由于作为哨兵节点的newHead初始定义为nil，这里不需要再移除哨兵节点
}

// findMiddle 找到中间节点
func (list *LinkedList) findMiddle() (node *Node) {

	// 使用快慢指针，当快指针走到链表尾部时，慢指针走到中点
	// 由于快慢指针都从节点1开始走，快指针只走奇数节点
	slow, fast := list.head, list.head
	for ; slow != nil && fast != nil; slow = slow.Next {
		fastNext := fast.Next
		// 快指针走到了节点尾部，链表有奇数个节点，慢指针走到了正中间
		if fastNext == nil {
			break
		}
		fast = fastNext.Next
		// 快指针的下个节点才为链表尾部，链表有偶数个节点，慢指针走到了前一半链表最后一个节点
	}

	return slow
}

// isPalindromic 回文字符串判断
func (list *LinkedList) isPalindromic() (result bool) {

	// 先找中点
	slow, fast := list.head, list.head
	for ; slow != nil && fast != nil; slow = slow.Next {
		fastNext := fast.Next
		if fastNext.Next == nil {
			break
		}
		fast = fastNext.Next
	}
	// 再反转后一半链表,中间节点的下个节点就是后半段的开始
	tailHead := slow
	var newTailHead *Node
	for ; tailHead != nil; tailHead = tailHead.Next {
		// 取出下个节点
		Next := tailHead.Next
		// 将旧头节点加入新链表
		tailHead.Next = newTailHead
		// 更新新链表
		newTailHead = tailHead
		// 更新旧链表头节点
		tailHead = Next
	}
	// 前后半截链表做比对
	for headAhead := list.head; newTailHead != nil; headAhead, newTailHead = headAhead.Next, newTailHead.Next {
		if headAhead.Data != newTailHead.Data {
			return false
		}
	}

	return true
}

// isCycle 成环检测
func (list *LinkedList) isCycle() (result bool, cycleEnter *Node, cycleLength int) {

	// 成环检测，快慢指针相遇
	slow, fast := list.head, list.head
	for ; slow != nil && fast != nil; slow = slow.Next {
		fastNext := fast.Next
		if fastNext == nil {
			result = false
			break
		}
		fast = fastNext.Next
		if slow.Next == fast {
			// 相遇的节点就是fast节点
			result = true
			break
		}
	}
	// 未成环不检测环入口和环长度
	if !result {
		return result, cycleEnter, cycleLength
	}
	// 环的入口，前后指针再次相遇为环的入口
	for cycleEnter = list.head; cycleEnter != fast; cycleEnter, fast = cycleEnter.Next, fast.Next {
	}
	// 环的长度
	for start := cycleEnter; start != cycleEnter; start = start.Next {
		cycleLength++
	}

	return
}

// removeLastN 删除链表倒数第N个节点
func (list *LinkedList) removeLastN(n int) (result bool) {
	// 如果成环是无法找到链表尾部的
	if result, _, _ := list.isCycle(); result {
		return false
	}
	// 先找到顺序第n个节点
	start := list.head
	step := 1
	for ; start != nil && step < n; start = start.Next {
		step++
	}
	if start == nil {
		// 说明链表长度不足
		return result
	}
	// 设置哨兵节点
	head := new(Node)
	head.Next = list.head
	for ; start.Next != nil; start, head = start.Next, head.Next {

	}
	// start.Next 为nil说明要删除的节点就是head的Next节点
	head.Next = head.Next.Next

	return true
}

// sortMerge 有序链表合并
func (list *LinkedList) sortMerge(otherList *LinkedList) {
	list.length += otherList.length
	// 待合并数据为空
	if otherList.head == nil {
		return
	}
	// 这里为了避免处理头节点变动的情况增加一个哨兵节点作为原链表头节点
	newHead := new(Node)
	newHead.Next = list.head
	list.head = newHead
	currNode := list.head
	headForMerge := otherList.head
	// 逐一插入待合并的节点
	for ; currNode.Next != nil && headForMerge != nil; currNode = currNode.Next {
		Next := currNode.Next
		// 当前节点数值大于待合并节点数值，将待合并节点放置在当前节点之前
		if headForMerge.Data <= Next.Data {
			NextHeadForMerge := headForMerge.Next
			currNode.Next = headForMerge
			headForMerge.Next = Next
			// 待合并节点更新
			headForMerge = NextHeadForMerge
			currNode = currNode.Next
		}
	}
	currNode.Next = headForMerge
	// 移除哨兵节点
	list.head = list.head.Next
}
